﻿// 0823train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>
#include <queue>

using namespace std;

/*
 这个相连位置在一个直线上，方向可以是水平的、垂直的、成对角线的或者反对角线的。 
注：学生个数不会超过 10000。

输入描述
输入的第一行为矩阵的行数和列数，接下来的 n 行为矩阵元素，元素间用 , 分隔。

输出描述
输出一个整数，表示矩阵中最长的位置相连的男生个数

3,4
F,M,M,F
F,M,M,F
F,F,F,M

输出3
 */

class Solution01
{
public:
    int result = 0;
    int curr_count = 0;
    void dfs(vector<vector<string>>& grid, vector<vector<bool>>&checked, vector<int>&dir_vec,
        int prev_r, int prev_c)
    {
        int curr_r = prev_r + dir_vec[0];
        int curr_c = prev_c + dir_vec[1];

        //越界，是否访问
        bool is_curr_r = curr_r >= 0 && curr_r < row_size;
        bool is_curr_c = curr_c >= 0 && curr_c < col_size;
        if (is_curr_r&&is_curr_c)
        {
            bool is_visited = checked[curr_r][curr_c];
            bool is_available = grid[curr_r][curr_c] == "M";

            if (!is_visited&&is_available)
            {
                curr_count += 1;
                //标记已访问
                checked[curr_r][curr_c] = true;
                dfs(grid, checked, dir_vec, curr_r, curr_c);
            }
        	
        }

    }
    void solve01(vector<vector<string>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                //目标值，且未访问
                if (grid[r][c]=="M")
                {
                    vector<bool>checked_status(col_size, false);
                    vector<vector<bool>>checked(row_size, checked_status);
                    //标记已访问
                    checked[r][c] = true;
                    for (auto&dir_vec:DirectionGrid)
                    {
                        //每个方向都要初始化一次
                        curr_count = 1;
                        dfs(grid, checked, dir_vec, r, c);
                        result = max(result, curr_count);
                    }

                }
                //for col_size
            }
            //for row_size
        }
        cout << result;
    }
private:
    vector<vector<int>>DirectionGrid = { {1,0},{0,1},{1,1} ,{1,-1}};
    int row_size = 0;
    int col_size = 0;
};


/*
 用数组表示：-1 0 1 1 1 0 1 0 1 1

棋子分布说明： 
1. -1代表白子，0代表空位，1 代表黑子 
2. 数组长度L，满足1 < L < 40，且L为奇数 

你得帮他写一个程序，
算出最有利的出子位置！
最有利定义 
1. 找到一个空位(0)，用棋子(1/-1)填充该位置，可以使得当前子的最大连续长度变大 
2. 如果存在多个符合要求的位置，返回最靠近中间的较小的那个坐标； 
3. 如果不存在可行位置，直接返回-1: 
4. 连续长度不能超过5个(五字棋约束)

输入描述
第一行: 当前出子颜色
第二行: 当前的棋局状态

输出描述
1个整数，表示出子位置的数组下标

输入
-1
-1 0 1 1 1 0 1 0 1 -1 1
输出
5
 */
class Solution02
{
//最有利的子位置，每一次放完，要统计当前最多的连续
//每一轮放完，更新curr_max_count
public:
    int curr_max_count = 0;
    vector<pair<int,int>>target_index_vec; //坐标，curr_max_count
    bool computedConstrain(vector<int>& status_vec, int use_num, int start)
    {
        bool is_equal_bigger = false;
        int vec_size = status_vec.size();
        
            int curr_num = status_vec[start];
            int curr_count = 1;
            for (int i=start-1;i>=0; i--)
            {
                if (status_vec[i] == curr_num)
                {
                    curr_count += 1;
                }
                else
                {
                    break;
                }
            }
			
            for (int i=start+1;i<vec_size; i++)
            {
	            if (status_vec[i]==curr_num)
	            {
                    curr_count += 1;
	            }
                else
                {
                    break;
                }
            }
            if (curr_count>=curr_max_count && curr_count<=5)
            {
                curr_max_count = curr_count;
                is_equal_bigger = true;
            }
        
        return is_equal_bigger;
    }

    void solve02(vector<int>&status_vec,int use_num)
    {
        for (int i=0; i<status_vec.size();i++)
        {
            int curr_num = status_vec[i];
            if (curr_num==0)
            {
                status_vec[i] = use_num;
                bool is_find = computedConstrain(status_vec, use_num, i);

                if (is_find)
                {
                    target_index_vec.push_back(make_pair(i, curr_max_count));
                }
                status_vec[i] = 0;
            }

        }
        if (target_index_vec.empty())
        {
            cout << -1;
            return;
        }

        vector<int>result_index_vec;

        for (auto&pair_item:target_index_vec)
        {
	        if (pair_item.second==curr_max_count)
	        {
                result_index_vec.push_back(pair_item.first);
	        }
        }

        if (result_index_vec.size()==1)
        {
            cout << result_index_vec[0];
            return;
        }

        int middle_pos = status_vec.size() / 2;
        int result = result_index_vec[0];
        for (int i=1; i<result_index_vec.size(); i++)
        {
            int curr_pos = result_index_vec[i];
            if (abs(curr_pos-middle_pos)<abs(result-middle_pos))
            {
                result = curr_pos;
            }
            else if (abs(curr_pos - middle_pos) == abs(result - middle_pos))
            {
				if (curr_pos<result)
				{
                    result = curr_pos;
				}
            }

        }
        cout << result;

    }
};

int coinChange(vector<int>& coins, int amount) {
    // 转移方程
    // dp[i]=min(dp[i],dp[i-coin])
    // 这里要取到amount，凑出amount所需的数量嘛
    // 初值全部设为amount+1, 模拟INT_MAX的情况
    int dp_size = amount + 1;
    vector<int> dynamic_vec(dp_size, amount + 1);
    // 凑出0 0个硬币
    dynamic_vec[0] = 0;

    for (auto& coin : coins) {
        //2 3
		for (int i = 1; i < dp_size; i++) {
            // 0 1 2 3 4 5 6
            if (i - coin < 0) {
                // 子问题无解
                continue;
            }
            // 子问题有解才赋值
            dynamic_vec[i] = min(dynamic_vec[i], 1 + dynamic_vec[i - coin]);
        }
        //for (auto&num:dynamic_vec)
        //{
        //    cout << num << ' ';
        //}
        //cout << '\n';
    }

    if (dynamic_vec[amount] == amount + 1) {
        return -1;
    }

    return dynamic_vec[amount];
    // solve05------
}

int solve02(int amount, vector<int>& coins)
{
    int dp_size = amount + 1;
    vector<long long>dynamic_vec(dp_size, 0);
    dynamic_vec[0] = 1;

    for (auto& num : coins)
    {
        for (int prev_sum = 0; prev_sum < dp_size; prev_sum++)
        {
            int curr_sum = num + prev_sum;
            int sum_count = dynamic_vec[prev_sum];

            if (curr_sum <= amount)
            {
                if (sum_count >= INT_MAX)
                {
                    dynamic_vec[curr_sum] = INT_MAX;
                    continue;
                }
                dynamic_vec[curr_sum] += sum_count;
            }

        }
        for (auto&num:dynamic_vec)
        {
            cout << num << ',';
        }
        cout << '\n';
    }


    return dynamic_vec[amount];
    //solve02-----
}


int main()
{
	{
        //coins = [1, 2, 5] amount = 5
        vector<int>coins = { 1, 2, 5 };
        int amount = 5;
        solve02(amount, coins);
        return 0;
	}
    {
        //coins = [1, 2, 5], amount = 11 3
        vector<int>coins = { 2,3 };
        int amount = 6;
        cout << coinChange(coins, amount);

        return 0;
    }
	
	{
        //int use_num;
        //cin >> use_num;
        //cin.ignore();
        //string input;
        //getline(cin, input);
        //
        string input = "0 -1 0 1 0 1 -1 -1 1 0 1 1 -1 -1 1 -1 -1 0 1 0 1 0 1 0 -1 0 -1 -1 -1 -1 1 -1 0";
        stringstream oh_sstream(input);
        vector<int>status_vec;
        string token;
        while (oh_sstream>>token)
        {
            status_vec.push_back(stoi(token));
        }
        int use_num = -1;
        
        Solution02 solu;
        solu.solve02(status_vec, use_num);

        return 0;
	}
/*
3,4
F,M,M,F
F,M,M,F
F,F,F,M

F,M,M,F
F,M,M,F
M,F,F,F
*/
    vector<vector<string>>grid;
    
    //string grid_size;
    //getline(cin, grid_size);

    //int pos1 = grid_size.find(',');
    //string row_size_str = grid_size.substr(0, pos1);
    //int row_size = stoi(row_size_str);
    //vector<string>str_vec(row_size);
    //for (int r=0; r<row_size; r++)
    //{
    //    string input;
    //    getline(cin, input);
    //    str_vec[r] = input;
    //}
    string str1 = "F,F,M,F";
    string str2 = "F,M,M,F";
    string str3 = "M,F,F,F";
    vector<string>str_vec = { str1,str2,str3 };
    for (auto&oh_str:str_vec)
    {
        stringstream oh_sstream(oh_str);
        string token;
        vector<string>mini_vec;
        while (getline(oh_sstream,token,','))
        {
            mini_vec.push_back(token);
        }
        grid.push_back(mini_vec);
    }
    
    Solution01 solu;
    solu.solve01(grid);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
